//
// Created by Jisam on 07/09/2024 8:59 PM.
// Solution of  c
//#pragma GCC optimize(3)
#include <bits/stdc++.h>

using namespace std;
#define endl "\n"
#define PSI pair<string,int>
#define PII pair<int,int>
#define PDI pair<double,int>
#define PDD pair<double,double>
#define VVI vector<vector<int>>
#define VI vector<int>
#define VS vector<string>
#define PQLI priority_queue<int, vector<int>, less<int>>
#define PQGI priority_queue<int, vector<int>, greater<int>>
#define code_by_jisam ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
typedef long long i64;
typedef unsigned u32;
typedef unsigned long long u64;
typedef __int128 i128;
int dx[] = {-1, 1, 0, 0, 1, 1, -1, -1,};
int dy[] = {0, 0, -1, 1, 1, -1, -1, 1,};

typedef long long ll;

ll qpow(ll a, ll b, ll p) {
    ll res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

ll inv(ll a, ll p) {
    return qpow(a, p - 2, p);
}

ll C(ll a, ll b, ll p) {
    if (b == 0 || b == a) return 1;
    if (b > a) return 0;
    ll numerator = 1, denominator = 1;
    for (ll i = 0; i < b; ++i) {
        numerator = numerator * (a - i) % p;
        denominator = denominator * (i + 1) % p;
    }
    return numerator * inv(denominator, p) % p;
}

ll lucas(ll a, ll b, ll p) {
    if (b == 0) return 1;
    ll a_mod_p = a % p;
    ll b_mod_p = b % p;
    return C(a_mod_p, b_mod_p, p) * lucas(a / p, b / p, p) % p;
}

void solution() {
    ll a, b, p;
    cin >> a >> b >> p;
    cout << lucas(a, b, p) << endl;
}

int main() {
    code_by_jisam;
    int T = 1;
    cin >> T;
    while (T--) {
        solution();
    }
    return 0;
}